package first.codeTop.tencent;

/**
 * @ClassName LC234
 * @description:
 * @author: 荣燊
 * @create: 2021-10-26 21:05
 **/
public class LC234 {
    public static void main(String[] args) {
        ListNode node = new ListNode(0);
        node.next = new ListNode(0);
//        node.next.next = new util.ListNode(2);
//        node.next.next.next = new util.ListNode(1);
        System.out.println(isPalindrome(node));
    }

    // 回文链表
    public static boolean isPalindrome(ListNode head) {
        if (head.next == null) {
            return true;
        }
        // 得到链表的总长度，并判断奇偶数
        int len = 0;
        ListNode temp = head;
        while (temp != null) {
            temp = temp.next;
            len++;
        }
        System.out.println("链表长度len="+len);
        // 开始将链表切分为两段
        int len1 = len / 2;
        if (len % 2 == 1) {
            len1 = len / 2 + 1;
        }
        System.out.println("链表一半的长度len1="+len1);
        ListNode temp2 = new ListNode();
        temp2.next = head;
        while (len1 > 0) {
            temp2 = temp2.next;
            len1--;
        }
        ListNode next = temp2.next;
        temp2.next = null;
        // 比较两个链表
        System.out.println("head.val="+head.val);
        System.out.println("next.val="+next.val);
        Boolean equal = isEqual(head, reverse1(next));
        return equal;
    }

    // 判断两链表是否相等
    public static Boolean isEqual(ListNode node1, ListNode node2) {
        boolean flag = false;
        while (node1 != null && node2 != null) {
            if (node1.val != node2.val) {
                return false;
            } else {
                flag = true;
            }
            node1 = node1.next;
            node2 = node2.next;
        }
        return flag;
    }

    // 反转链表
    public static ListNode reverse1(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }

    public static ListNode reverse2(ListNode head) {
        if (head.next != null) {
            return head;
        }
        ListNode node = reverse2(head.next);
        head.next.next = head;
        head.next = null;
        return node;
    }
}
